package LeetCodeDemo;

import java.util.HashSet;
import java.util.Set;

/***
 * 给定一个字符串s ，请你找出其中不含有重复字符的最长子串长度
 *
 *
 * 示例 1:
 *
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 *
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 *
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 */
public class LeetCode3 {
    public int lengthOfLongestSubString(String s){
        //哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        //右指针，初始值为-1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1;
        int ans = 0 ;

        for (int i = 0; i < s.length(); i++) {
            if (i != 0){
                //左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk+1))){
                occ.add(s.charAt(rk+1));
                ++rk;
            }
            ans = Math.max(ans,rk-i+1);
        }
        return ans;
    }

    public static void main(String[] args) {
        LeetCode3 leetCode3 = new LeetCode3();
        int qwertyyq = leetCode3.lengthOfLongestSubString("qwertyyq");
        System.out.println("jfksf="+qwertyyq);
    }
}
/****************************************************************************************
 *
 * 这道题主要用的思路是：滑动窗口
 * 什么是滑动窗口？
 * 其实就是一个队列。比如 abcabcbb，进入这个队列（窗口）为abc满足题目要求，当再进入a，队列变成了abca
 * 这时候不满足要求，所以我们要移动这个队列
 * 如何移动？
 * 我们只要把队列的左边的元素移出就行了，直到满足题目要求
 * 一直维持这样的队列，找出队列出现最长的长度时候，求出解
 * 时间复杂度O(n)
 *
 *
****************************************************************************************/